﻿

#define  _CRT_SECURE_NO_WARNINGS 1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_TREE_NODES 256

typedef struct Node {
    char data;
    int frequency;
    struct Node* left;
    struct Node* right;
} Node;

Node* createNode(char data, int frequency) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->frequency = frequency;
    newNode->left = newNode->right = NULL;
    return newNode;
}

void swapNodes(Node** a, Node** b) {
    Node* t = *a;
    *a = *b;
    *b = t;
}

void heapify(Node* nodes[], int size, int index) {
    int smallest = index;
    int left = 2 * index + 1;
    int right = 2 * index + 2;

    if (left < size && nodes[left]->frequency < nodes[smallest]->frequency)
        smallest = left;

    if (right < size && nodes[right]->frequency < nodes[smallest]->frequency)
        smallest = right;

    if (smallest != index) {
        swapNodes(&nodes[index], &nodes[smallest]);
        heapify(nodes, size, smallest);
    }
}

void buildMinHeap(Node* nodes[], int size) {
    int i, startIdx = (size / 2) - 1;

    for (i = startIdx; i >= 0; --i) {
        heapify(nodes, size, i);
    }
}

Node* extractMin(Node* nodes[], int* size) {
    Node* minNode = nodes[0];
    nodes[0] = nodes[*size - 1];
    --(*size);
    heapify(nodes, *size, 0);
    return minNode;
}

void insertMinHeap(Node* nodes[], int* size, Node* node) {
    int i = (*size)++;
    while (i && node->frequency < nodes[(i - 1) / 2]->frequency) {
        nodes[i] = nodes[(i - 1) / 2];
        i = (i - 1) / 2;
    }
    nodes[i] = node;
}

void printCodes(Node* root, int arr[], int top) {
    if (root->left) {
        arr[top] = 0;
        printCodes(root->left, arr, top + 1);
    }
    if (root->right) {
        arr[top] = 1;
        printCodes(root->right, arr, top + 1);
    }
    if (!root->left && !root->right) {
        printf("%c: ", root->data);
        for (int i = 0; i < top; ++i) {
            printf("%d", arr[i]);
        }
        printf("\n");
    }
}

void huffmanCodes(char data[], int freq[], int size) {
    Node** nodes = (Node**)malloc(size * sizeof(Node*));
    int i;
    for (i = 0; i < size; ++i) {
        nodes[i] = createNode(data[i], freq[i]);
    }

    buildMinHeap(nodes, size);

    while (size > 1) {
        Node* left = extractMin(nodes, &size);
        Node* right = extractMin(nodes, &size);
        Node* newNode = createNode('$', left->frequency + right->frequency);
        newNode->left = left;
        newNode->right = right;
        insertMinHeap(nodes, &size, newNode);
    }

    int codes[100];
    printCodes(nodes[0], codes, 0);

    free(nodes);
}

int main() {
    char data[] = { 'A', 'B', 'C', 'D', 'E', 'F' };
    int freq[] = { 15, 10, 8, 12, 10, 5 };
    int size = sizeof(data) / sizeof(data[0]);

    huffmanCodes(data, freq, size);

    return 0;
}
